Leetcode-House Robber

发表于 | 分类于 |

House Robber

打家劫舍。问题本质就是从数组中找出一个或多个不相邻的数，使其和最大。

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Description

解题思路：

  1. 如果选择了抢劫上一个屋子，那么就不能抢劫当前的屋子，所以最大收益就是抢劫上一个屋子的收益；
  2. 如果选择抢劫当前屋子，就不能抢劫上一个屋子，所以最大收益是到上一个屋子的上一个屋子为止的最大收益，加上当前屋子里有的钱。

令dp[i]表示从[0, …, i]数组中能够得到的最大收益，显然，dp[0]=nums[0], dp[1]=max(dp[0],dp[1]), 现在计算dp[i+1]:

dp[i+1]=max(dp[i], dp[i-1]+nums[i+1])

其中，上式包含了如下隐含信息：
若dp[i]不包含nums[i], 所以nums[i+1]可以和dp[i]相加，但此时dp[i]=dp[i-1],所以dp[i-1]+nums[i+1]与dp[i]+nums[i+1]的值相等；
若dp[i]包含nums[i]，则nums[i+1]不可以和dp[i]相加，所以只存在nums[i+1]+dp[i-1]。

实际计算时只需要保存两个变量即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)<=1:
            return 0 if len(nums)==0 else nums[0]
        # 保存上一次的收益
        last = nums[0]
        # 保存当前收益
        cur = max(nums[0], nums[1])
        for i in range(2, len(nums)) :
            tmp = cur
            cur = max(last+nums[i], cur)
            last = tmp
        return cur

tip:
python中的三目运算符不像其他语言, 其他的一般都是:

判定条件?为真时的结果:为假时的结果

而在python中的格式为:

为真时的结果 if 判定条件 else 为假时的结果